#!/usr/bin/perl
use strict;
use Data::Dump qw(dump);

my $MATRIX_SZ = 10000;
my $PROPORTION  = int ( ($MATRIX_SZ * ( $MATRIX_SZ - 1) * 0.5) * 0.007);
#print STDERR "PROPORTION = $PROPORTION\n";

sub min($$)
{
	return ($_[0] < $_[1]) ? $_[0] : $_[1];
}
sub get_num_values(\@$)
{
	my ($counts,  $desired_total) = @_;
	
	my $curr_total = 0;
	for (my $i = 0; $i < $MATRIX_SZ; ++$i)
	{
		$counts->[$i] = $i;
		$curr_total += $i;
	}
	while ($curr_total > $desired_total)
	{
		my $col = rand($MATRIX_SZ);
		# each row has at least 1 element
		next if ($counts->[$col] <= 1);
		my $possible = min($counts->[$col], $curr_total - $desired_total);
		my $remove = int(rand($possible)) + 1;
		#print STDERR "$counts->[$col] - 1, $curr_total - $desired_total)=>";
		#print STDERR $possible, ",";
		#print STDERR $remove, "\n";
		$curr_total -=$remove;
		$counts->[$col] -= $remove;
	}
	#print STDERR "num_values\n";
}
sub randomize_counts(\@)
{
	my ($counts) = @_;
	my $sz = @$counts;
	for (my  $i = 0; $i < $sz; ++$i)
	{
		my $i = int(rand($sz));
		my $j = int(rand($i + $sz) % $sz);
		($counts->[$i], $counts->[$j]) = ($counts->[$j], $counts->[$i]);
	}
	
}

	my @values;

	
	# get number of values per row (randomly)
	my @counts = (0) x $MATRIX_SZ;
	get_num_values(@counts, $PROPORTION);

	
	
	print STDERR "\tNumber of values per row decided\n";

	my $cnt_filled	= 0;
	for (my $row = 0; $row < $MATRIX_SZ; ++$row)
	{
		$values[$row ][$row] = 0.0; 
		my $count_values_in_row = $counts[$row];
		next unless $count_values_in_row;
		my @indices = (0..($count_values_in_row-1));
		randomize_counts(@indices);
		#print STDERR dump(@indices), "\n";
		my @sorted_indices = sort {$a <=> $b } @indices[0..($count_values_in_row - 1)];
		for my $col(@sorted_indices)
		{
			#print STDERR "values[$col][$row ]\n";
			$values[$row ][$col] = 
			$values[$col][$row ] = rand(1000);
			++$cnt_filled;
		}
	}

	for my $row (0..($MATRIX_SZ - 1))
	{
		for my $col (0..($MATRIX_SZ - 1))
		{
			if (defined ($values[$col][$row]))
			{
				print "A$row\tA$col";
				print "\t$values[$col][$row]\n";
			}
		}
	}
	
	print STDERR "\t\t" , $cnt_filled , " diagonal values filled.\n";

